# 植物生命力(好题)
from collections import defaultdict
from functools import cache
import sys

sys.setrecursionlimit(100000)


def count_node(node_vals, edges, root):
    # 构建树结构
    tree = defaultdict(list)
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)
    res = 0

    def dfs(curr_idx, pa_idx):
        """这个dfs写得很巧妙"""
        nonlocal res, node_vals
        children = []
        for c in tree[curr_idx]:
            if c != pa_idx:
                children += dfs(c, curr_idx)
        for child in children:
            if node_vals[child - 1] < node_vals[curr_idx - 1] and node_vals[curr_idx - 1] % node_vals[child - 1] != 0:
                res += 1
        children.append(curr_idx)
        return children

    dfs(root, -1)

    return res


def solve(val, edges, root):
    n = len(val)
    root -= 1
    g = [[] for _ in range(n)]
    for x, y in edges:
        x -= 1
        y -= 1
        g[x].append(y)
        g[y].append(x)

    res = 0

    def dfs(x, pa):
        s = []
        for y in g[x]:
            if y != pa:
                s += dfs(y, x)
        nonlocal res
        for v in s:
            if v < val[x] and val[x] % v != 0:
                res += 1
        s.append(val[x])
        return s

    dfs(root, -1)
    return res


# n, s = map(int, input().split())
# node_vals = list(map(int, input().split()))
# edges = []
# for i in range(n - 1):
#     edges.append(tuple(map(int, input().split())))
root = 1
node_vals = [6, 5, 3, 2, 4, 1]
edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)]
print(count_node(node_vals, edges, root))
print(solve(node_vals, edges, root))

root = 1
node_vals = [6, 5, 3, 2, 3, 1]
edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6)]
print(count_node(node_vals, edges, root))
print(solve(node_vals, edges, root))

edges = []
with open("../../data/2024_h.in", "r") as file:
    n, root = map(int, file.readline().split())
    node_vals = list(map(int, file.readline().split()))
    for i in range(n - 1):
        edges.append(tuple(map(int, file.readline().split())))
print(count_node(node_vals, edges, root))
print(solve(node_vals, edges, root))
